1. Field of the Invention
The present invention relates generally to an encoding apparatus and method in a communication system. In particular, the present invention relates to an apparatus and method for encoding a low density parity check (LDPC) code in a communication system.
2. Description of the Related Art
A communication system typically performs encoding on transmission data prior to transmission of the data. Such an encoding method includes an iterative encoding technique, a convolutional encoding technique, a turbo encoding technique, and a low density parity encoding technique. The encoding techniques can be uniquely used according to their characteristics, and research is currently being conducted on the low density parity encoding technique which is expected to be used in a next generation mobile communication system.
The low density parity encoding technique is a type of block encoding for encoding information bits using an encoding matrix before transmission of data. A method of performing the block encoding using an encoding matrix in which the number of elements of ‘1’ is very small, i.e., most elements thereof have a value of ‘0’, is called the “low density parity encoding technique”. Such a low density parity encoding technique uses a parity check matrix comprised of rows and columns each having a spare value of ‘1’. The rows and columns each can express a structure of a code using a factor graph to which a check node and a variable node are mapped. Iterative decoding can be achieved based on a sum-product algorithm defined by the factor graph. An iterative decoding process performed on the factor graph can be implemented in a parallel structure, and can greatly reduce decoding time due to performing such a parallel process. Compared with a turbo code, an LDPC code has a low frame error rate (FER) because the LDPC code, compared with the turbo code, has a larger minimum distance as a block size increases. In addition, the LDPC code generally does not show an error floor even at a relatively high signal-to-noise ratio (SNR). Further, the LDPC code can perform error detection and efficient decoding interruption on a decoded codeword even without the performance of a cyclic redundancy check (CRC) by using orthogonality of a codeword and a parity check matrix.
However, the LDPC code is limited in that an encoding process of calculating a codeword for input information using a parity check matrix is complex compared with that of the turbo code. That is, while the turbo code can undergo real-time encoding in a simple manner via iteration by a recursive systematic convolutional encoder, the LDPC code has encoding complexity approaching a square of a block length according to a structure of a parity check matrix that defines the code.
A description will now be made of known methods for generating a parity check matrix for the LDPC code.
Construction Method by MacKay and Neal
MacKay and Neal have proposed the following M×N parity check matrix generation method in a paper where they have newly introduced an LDPC code.
Structure 1
An M×N parity check matrix is randomly generated such that the number of is in each column is fixed at ‘t’ and the number of 1s in each row is constant, if possible. In addition, the M×N parity check matrix is randomly generated such that an overlap between two particular columns does not exceed ‘1’ to prevent the occurrence of a length=4 cycle. FIG. 1A illustrates a structure of a rate=½ matrix in which the number of 1s in each column is 3. In FIG. 1A, arrows on circles denoted by reference numerals 101 and 103 indicate that even though any row and column are selected from the matrix, the number of 1s in the selected row and column is 3.
Structure 2
Columns with a weight 2 are generated for the first M/2 columns such that two particular columns should not overlap with each other, and columns with a weight 3 are randomly generated for the remaining columns such that an overlap between two particular columns should not exceed 1. FIG. 1B illustrates a structure of a rate=⅓ matrix constructed such that an overlap between two particular columns with a weight 3 should not exceed 1. In FIG. 1B, diagonals denoted by reference numerals 111 and 113 indicate that the matrix has the stated number of 1s, and an arrow on a circle denoted by a reference numeral 115 indicates that even though any row and column are selected from the matrix, the number of 1s in the selected row and column is 3.
Structure 1 and Structure 2
Several columns are removed from the parity check matrix so that a cycle of a particular length 1 should not occur when the parity check matrix generated by FIGS. 1A and 1B is expressed with a factor graph. In this manner, a parity check matrix satisfying the two structures illustrated in FIGS. 1A and 1B can be constructed.
In addition, parity check matrixes shown in FIGS. 1C and 1D can be generated through a non-overlapping permutation matrix. In FIGS. 1C and 1D, arrowed circles or elliptic curves indicate random permutations of columns. A method of FIG. 1C is identical to a parity check matrix generation method proposed by Gallager. Thereafter, MacKay has proposed a method of generating a parity check matrix shown in FIG. 2 taking efficient encoding and decoding performances into account. In the matrix of FIG. 2, if it is assumed that the total number of rows is n and the total number of columns is n−k, 1s are arranged in a diagonal direction denoted by reference numeral 201 for (n−k) elements from a (k+1)th element, and if the parity check matrix is constructed such that even though any row and column are selected at the last part denoted by reference numeral 203 the number of 1s in the selected row and column is 3, it is noted that decoding performance is improved.
The methods proposed by MacKay and Neal correspond to an earlier version of the LDPC code generation method. However, conventional parity check matrix generation methods have difficulty in reducing encoding complexity and also have difficulty in generating LDPC codes having various code rates and various block sizes.
Construction Method by Generalized LDPC Code
T. Zahng and K. Parhi have generated a generalized LDPC code structure-based parity check matrix that can be efficiently encoded and decoded, and have implemented a 54-Mbps decoder for LDPC codes with a field programmable gate array (FPGA), using the generated parity check matrix. Zahng and Parhi have generated a (3,6) regular LDPC code by constructing a parity check matrix in the following type, and have proposed a structure of a partly parallel decoder for the generated (3,6) regular LDPC code. The proposed structure has the following form.
  H  =      [                                        H            1                                                            H            2                                                            H            3                                ]  
In FIG. 3, each of sub-matrixes Ix,y constituting H1 is an L×L unit matrix, and each of sub-matrixes Px,y constituting H2 is a cyclic-shifted form of the L×L unit matrix. That is, if Tu(Q) is defined as a right shift operation on each column in a matrix Q by u, Px,y is an L×L matrix that satisfiesPx,y=Tu(I), where u=((x−1)·y)modL  (1)
It should be understood from Equation (1) that if a parity check matrix for an LDPC code is constructed with a sub-matrix H3 located in the bottom of FIG. 3, it becomes a random parity check matrix in which H does not have a cycle value of 4. A partly parallel LDPC decoder that simultaneously performs variable node processing and check node processing on each of sub-matrixes through a T. Zahng and K. Parhi's parity check matrix having a structure shown in FIG. 3 was implemented. That is, the decoder was implemented such that it has a total of K2 variable node units (VNUs) each having L memory locations, has k check node units (CNUs) for each sub-matrix, and updates memory locations through connections for them every clock. Therefore, 2L clocks are required for one iteration.
A structure of the decoder is characterized in that an LDPC code was designed based on the concept of a generalized LDPC structure and a partly parallel decoder for it was actually implemented through Xilinx Virtex FPGA. However, the decoder lacks flexibility for more various code rates and block sizes, and cannot secure efficient systematic encoding.
Construction by Semi-Random Parity Check Matrix
L. Ping et al. have proposed a new method for constructing a parity check matrix for an LDPC code using a semi-random technique. That is, they have proposed a method for separating a parity check matrix into two sub-matrixes, and generating only one sub-matrix in a random manner and the other sub-matrix in a deterministic manner. In addition, they have shown through experiment that more efficient real-time encoding is possible by constructing the parity check matrix in this manner and decoding performance is also not inferior to that of a fully random parity check matrix.
A semi-random parity check matrix H is comprised of two sub-matrixes, as defined by H=[Hd|Hp]. Here, Hp denotes an (n−k)×(n−k) sub-matrix corresponding to a parity part of the parity check matrix H, and Hd denotes an (n−k)×k sub-matrix corresponding to an information part of the parity check matrix H. A particular codeword c is also constructed in the form of c=[cd|cp], where cd denotes a part corresponding to a systematic information symbol of the codeword c and cp denotes a part corresponding to a parity symbol of the codeword c. The parity part Hp of the parity check matrix H is constructed in the form of a deterministic dual-diagonal matrix as shown below.
                              H          p                =                  (                                                    1                                            0                                            ⋯                                            0                                                                    1                                            1                                            ⋯                                            0                                                                    0                                            ⋰                                            ⋰                                            0                                                                    0                                            0                                            1                                            1                                              )                                    (        2        )            
Further, it has been proposed that the information part Hd of the parity check matrix H be randomly generated, with a column weight and a row weight maintained. If the Hp and the Hd are constructed in this manner and the parity check matrix H is constructed according thereto, each parity symbol is constructed using orthogonality of the parity check matrix and the codeword as shown below.
                                                                        [                                                      H                    d                                    |                                      H                    p                                                  ]                            ⁡                              [                                                      c                    d                                    |                                      c                    p                                                  ]                                      T                    =                                    0              ⁢                                                          ⁢                              □                                                                  ⁢                                  p                  1                                                      =                                                            ∑                  j                                                                                        ⁢                                                                  ⁢                                                      h                                          i                      ,                      j                                        d                                    ⁢                                      d                    j                                    ⁢                                                                          ⁢                  and                  ⁢                                                                          ⁢                                      p                    i                                                              =                                                p                                      i                    -                    1                                                  +                                                      ∑                    j                                                                                                  ⁢                                                                          ⁢                                                            h                                              i                        ,                        j                                            d                                        ⁢                                          d                      j                                                                                                          ⁢                                                      (        3        )            
Based on Equation (3), (n−k) parity symbols can be simply calculated on a real-time basis using input information symbols.
R. Echard et al. have proposed a simply encoder structure capable of performing real-time encoding using Equation (4) below based on the fact that an inverse matrix of a dual-diagonal matrix is a triangular matrix.
                                                                                          H                  P                                ⁢                                  c                  P                                            =                              v                =                                                                            H                      d                                        ⁢                                          c                                              d                        ⁢                                                                                                                                        ⁢                                                                                  ⁢                                          □                                                                                          ⁢                                              c                        P                                                                              =                                                                                    [                                                  H                          P                                                ]                                                                    -                        1                                                              ⁢                    v                                                                                                                                                            where                  ⁢                                                                          [                                      H                    P                                    ]                                                  -                  1                                            =                                                (                                                                                    1                                                                    0                                                                    ⋯                                                                    0                                                                                                            1                                                                    1                                                                    ⋯                                                                    0                                                                                                            1                                                                    ⋰                                                                    ⋰                                                                    0                                                                                                            1                                                                    1                                                                    1                                                                    1                                                                              )                                :                                                                  ⁢                                  Lower                  ⁢                                                                          ⁢                  triangular                  ⁢                                                                          ⁢                  matrix                                                                                        (        4        )            
For an efficient decoder structure, R. Echard et al. subdivided the sub-matrix Hd into new sub-matrixes. Each of the sub-matrixes was defined by a π-rotation pattern for a particular permutation matrix. A sub-matrix Hd of a parity check matrix for a rate=½ LDPC code is constructed as shown below.
                              H          d                =                  [                                                                      π                  A                                                                              π                  B                                                                              π                  C                                                                              π                  D                                                                                                      π                  B                                                                              π                  C                                                                              π                  D                                                                              π                  A                                                                                                      π                  C                                                                              π                  D                                                                              π                  A                                                                              π                  B                                                                                                      π                  D                                                                              π                  A                                                                              π                  B                                                                              π                  C                                                              ]                                    (        5        )            
If a sub-matrix πA constituting the Hd is defined as a permutation matrix for a particular unit matrix, πB, πC and πD denote sub-matrixes determined by rotating the sub-matrix πA by −π/2, π and π/2, respectively.
R. Echard et al. have proposed an LDPC code that can be simply encoded, the LDPC code being capable of obtaining relatively excellent performance by constructing a parity check matrix in the above-stated manner. However, they have scarcely mentioned the π-rotation pattern for generating parity check matrixes corresponding to other code rates except the rate ½. Therefore, research should be conducted on technology related to the π-rotation pattern, and it is difficult to apply the state-of-the-art technology to the system.
Each of the three types of LDPC codes described above has advantages and disadvantages. For example, disadvantageously, the LDPC codes cannot be processed on a real-time basis, and cannot be easily extended. Therefore, the current mobile communication system has difficulty in using the LDPC code for an encoding technique, and even the next generation mobile communication system cannot employ the methods stated above.